package com.isaiah.queue;


import java.util.LinkedList;
import java.util.TreeMap;
import java.util.PriorityQueue;

/**
 * @Title: ${file_name}
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/5/2520:25
 */
class Solution {

    private class Freq{
        int e;
        int freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        // 定义一个Map记录数字对应的次数，key为数字， value为数字对应的次数
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums){
            if (map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }
            else{
                map.put(num, 1);
            }
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)->map.get(o1) - map.get(o2));
        for (int key : map.keySet()){
            if (queue.size() < k){
                // 进队
                queue.add(key);
            }
            // 弹出堆顶元素，再进队
            else if (map.get(key) > map.get(queue.peek()) ){
                queue.remove();
                queue.add(key);
            }
        }
        // 把队列中元素，不断弹出堆顶元素，放入一个数组中
        LinkedList<Integer> res = new LinkedList<>();
        while (!queue.isEmpty()){
            res.add(queue.remove());
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}